{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Greater Element III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextGreaterElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个更大元素 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>n</code> ，请你找出符合条件的最小整数，其由重新排列 <code>n</code><strong> </strong>中存在的每位数字组成，并且其值大于 <code>n</code> 。如果不存在这样的正整数，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>注意</strong> ，返回的整数应当是一个 <strong>32 位整数</strong> ，如果存在满足题意的答案，但不是 <strong>32 位整数</strong> ，同样返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 12\n",
    "<strong>输出：</strong>21\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 21\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-greater-element-iii](https://leetcode.cn/problems/next-greater-element-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-greater-element-iii](https://leetcode.cn/problems/next-greater-element-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12', '21']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        greater = self.next_greater(nums2)\n",
    "        greater_map = {}\n",
    "        for i in range(len(nums2)):\n",
    "            greater_map[nums2[i]] = greater[i]\n",
    "        res = [0] * len(nums1)\n",
    "        for i in range(len(nums1)):\n",
    "            res[i] = greater_map[nums1[i]]\n",
    "        return res\n",
    "    def next_greater(self, nums):\n",
    "        n = len(nums)\n",
    "        res = [0 for _ in range(n)]\n",
    "        s = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while s and s[-1] <= nums[i]:\n",
    "                s.pop()\n",
    "            res[i] = s[-1] if s else -1\n",
    "            s.append(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        output=[]\n",
    "        for i in nums1:\n",
    "            index=nums2.index(i)\n",
    "            for j in nums2[index:]:\n",
    "                if j>i:\n",
    "                    output.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                output.append(-1)\n",
    "        return output\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dmap = {}\n",
    "        stack = []\n",
    "        for n in nums2:\n",
    "            while stack and stack[-1]<n:\n",
    "                dmap[stack.pop()] = n\n",
    "            stack.append(n)\n",
    "        return [dmap.get(n,-1) for n in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        for i in nums1:\n",
    "            start = nums2.index(i)+1\n",
    "            if start==len(nums2):\n",
    "                res.append(-1)\n",
    "            elif start==len(nums2)-1:\n",
    "                if nums2[-1]>i:\n",
    "                    res.append(nums2[-1])\n",
    "                else:\n",
    "                    res.append(-1)\n",
    "            else:\n",
    "                flag=1\n",
    "                for j in nums2[start:]:\n",
    "                    if j>i:\n",
    "                        res.append(j)\n",
    "                        flag=0\n",
    "                        break\n",
    "                if flag:\n",
    "                    res.append(-1)\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        dict = {}\n",
    "        \n",
    "        for i in nums2:\n",
    "            while len(stack) and stack[-1] < i:\n",
    "                dict[stack.pop()] = i\n",
    "            stack.append(i)    \n",
    "        for j in range(len(nums1)):\n",
    "            nums1[j] = dict.get(nums1[j],-1)\n",
    "        return nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        dict = {}\n",
    "        \n",
    "        for i in nums2:\n",
    "            while len(stack) and stack[-1] < i:\n",
    "                dict[stack.pop()] = i\n",
    "            stack.append(i)    \n",
    "        for j in range(len(nums1)):\n",
    "            nums1[j] = dict.get(nums1[j],-1)\n",
    "        return nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        for i1 in nums1:\n",
    "            # print(1,end=\" \")\n",
    "            for i2 in nums2:\n",
    "                # print(2,end=\" \")\n",
    "                if i2 == i1:\n",
    "                    # print(3,end=\" \")\n",
    "                    idx = nums2.index(i2)\n",
    "                    nums3 = nums2[idx:]\n",
    "                    for i in nums3:\n",
    "                        if i > i2:\n",
    "                            stack.append(i)\n",
    "                            break\n",
    "                    else:\n",
    "                        stack.append(-1)\n",
    "                        break\n",
    "        return stack\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        for i1 in nums1:\n",
    "            # print(1,end=\" \")\n",
    "            for i2 in nums2:\n",
    "                # print(2,end=\" \")\n",
    "                if i2 == i1:\n",
    "                    # print(3,end=\" \")\n",
    "                    idx = nums2.index(i2)\n",
    "                    nums3 = nums2[idx:]\n",
    "                    for i in nums3:\n",
    "                        if i > i2:\n",
    "                            stack.append(i)\n",
    "                            break\n",
    "                    else:\n",
    "                        stack.append(-1)\n",
    "                        break\n",
    "        return stack\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        ans = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i == j:\n",
    "                    temp = nums2.index(j)\n",
    "                    break\n",
    "            flag = False\n",
    "            for t in nums2[temp + 1:]:\n",
    "                if t > i:\n",
    "                    flag = True\n",
    "                    ans.append(t)\n",
    "                    break\n",
    "            if flag == False:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        index, value = {}, {}\n",
    "        for i,v in enumerate(nums2):\n",
    "            index[i] = v\n",
    "            value[v] = i \n",
    "\n",
    "        for i,v in enumerate(nums1):\n",
    "            j = value[v]\n",
    "            while index.get(j+1) is not None:\n",
    "                tmp = index[j+1]\n",
    "                if tmp > v:\n",
    "                    nums1[i] = tmp\n",
    "                    break\n",
    "                j += 1\n",
    "            else:\n",
    "                nums1[i] = -1\n",
    "        \n",
    "        return nums1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack, hashmap = list(), dict()\n",
    "        for i in nums2:\n",
    "            while len(stack) != 0 and stack[-1] < i:\n",
    "                hashmap[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        return [hashmap.get(i, -1) for i in nums1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        l = len(nums2)\n",
    "        for i in range(l):\n",
    "            if nums2[i] not in dic:\n",
    "                dic[nums2[i]] = i\n",
    "        ans = [-1]*len(nums1)\n",
    "        l1 = len(nums1)\n",
    "        for j in range(l1):\n",
    "            index = dic[nums1[j]]\n",
    "            for i in range(index,l):\n",
    "                if nums2[i]>nums1[j]:\n",
    "                    ans[j] = nums2[i]\n",
    "                    break\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        dict1 = {}\n",
    "        stack = []\n",
    "        for i in range(len(nums2)):\n",
    "            if not stack:\n",
    "                stack.append(nums2[i])\n",
    "                continue\n",
    "            while stack and stack[-1]<nums2[i]:\n",
    "                dict1[stack.pop()] = nums2[i]\n",
    "            stack.append(nums2[i])\n",
    "        res = []\n",
    "        for num in nums1:\n",
    "            if num in dict1:\n",
    "                res.append(dict1[num])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# intuition: \n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        book = {}\n",
    "        stack = [float('inf')]\n",
    "        res = []\n",
    "        for num in nums2:\n",
    "            while stack[-1] < num:\n",
    "                book[stack.pop()] = num\n",
    "            stack.append(num)\n",
    "        for num in nums1:\n",
    "            if num in book:\n",
    "                res.append(book[num])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        if not nums2 or not nums1:\n",
    "            return [-1] * len(nums1)\n",
    "        stack = [nums2[0]]\n",
    "        hashMap = {}\n",
    "        i = 1\n",
    "        while i < len(nums2):\n",
    "            while stack and nums2[i] > stack[-1]:\n",
    "                hashMap[stack[-1]] = nums2[i]\n",
    "                stack.pop()\n",
    "            stack.append(nums2[i])\n",
    "            i += 1\n",
    "        while stack:\n",
    "            hashMap[stack.pop()] = -1\n",
    "        res = [hashMap[num] for num in nums1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        l=[]\n",
    "        N=len(nums1)\n",
    "        M=len(nums2)\n",
    "        for i in range(N):\n",
    "            j=0\n",
    "            while j<M:\n",
    "                if nums2[j]==nums1[i]:\n",
    "                    if j==M-1:\n",
    "                        l.append(-1)\n",
    "                        break\n",
    "                    j+=1\n",
    "                    while j<M:\n",
    "                        if nums2[j]>nums1[i]:\n",
    "                            l.append(nums2[j])\n",
    "                            break \n",
    "                        else:\n",
    "                            j+=1\n",
    "                            if j==M:\n",
    "                                l.append(-1)\n",
    "                    break\n",
    "                else:\n",
    "                    j+=1\n",
    "            \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # l = []\n",
    "        # for i in range(len(nums1)):\n",
    "        #     for j in range(nums2.index(nums1[i])+1,len(nums2)):\n",
    "        #         if nums2[j]>nums1[i]:\n",
    "        #             l.append(nums2[j])\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             l.append(-1)\n",
    "        # return l\n",
    "        res = []\n",
    "        for i in nums1:\n",
    "            for j in nums2[nums2.index(i)+1:]:\n",
    "                if j > i:\n",
    "                    res.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # d = {}\n",
    "        # stack = []\n",
    "        # for i in range(len(nums2)-1,-1,-1):\n",
    "        #     while len(stack) > 0 and stack[-1] < nums2[i]:\n",
    "        #         stack.pop()\n",
    "        #     if len(stack) == 0:\n",
    "        #         d[nums2[i]] = -1\n",
    "        #     else:\n",
    "        #         d[nums2[i]] = stack[-1]\n",
    "        #     stack.append(nums2[i])\n",
    "        #     # print(\"nums2[%d] = %d,d[nums2[%d]] = %d\"%(i,nums2[i],i,d[nums2[i]]))\n",
    "\n",
    "        # for i in range(len(nums1)-1,-1,-1):\n",
    "        #     nums1[i] = d[nums1[i]]\n",
    "        #     # print(\"nums1[i] = %d\"%(nums1[i]))\n",
    "        #     # print(\"d[nums1[i]] = %d\"%(d[nums1[i]]))\n",
    "        # return nums1\n",
    "        dic, stack = {}, []\n",
    "        for i in range(len(nums2) - 1, -1, -1):\n",
    "            while stack and stack[-1] <= nums2[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                dic[nums2[i]] = stack[-1]\n",
    "            stack.append(nums2[i])\n",
    "        return [dic.get(num, -1) for num in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        res = []#初始化结果和栈\n",
    "        stack = []\n",
    "        for num in nums2:#nums2 全部入栈1\n",
    "            stack.append(num)\n",
    "        for num in nums1:#遍历子集nums1\n",
    "\n",
    "            temp = []#初始化另一个栈\n",
    "            maximum = -1 #初始化两个辅助参数（maximum 是结果， isFound 是遍历栈1停的条件）\n",
    "            isFound = False\n",
    "\n",
    "            while (len(stack) != 0 and not isFound):#遍历栈1\n",
    "                top = stack.pop()#top是栈1的栈顶元素\n",
    "                if top > num:#有可能的结果\n",
    "                    maximum = top\n",
    "                elif top == num:#结束的条件\n",
    "                    isFound = True\n",
    "                temp.append(top)\n",
    "            \n",
    "            res.append(maximum)#对于nums1中的每一个数，增加一个结果（跟着for循环变）\n",
    "\n",
    "            while (len(temp) != 0):#对于每次forloop，把temp弄回stack里（还原）\n",
    "                stack.append(temp.pop())\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        tmp = []\n",
    "        for i in nums1:\n",
    "            j = nums2.index(i)\n",
    "            isfound = False\n",
    "            while j < len(nums2)-1:\n",
    "                if nums2[j+1] > i:\n",
    "                    tmp.append(nums2[j+1])\n",
    "                    isfound = True\n",
    "                    break\n",
    "                j += 1\n",
    "            if isfound == False:\n",
    "                tmp.append(-1)\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        1. 求下一个更大大元素-> 使用单调栈\n",
    "        2. 要在nums2里面寻找，遍历nums2\n",
    "        3. 栈里只存放nums1有的元素，因为只计算nums1的下一个更大\n",
    "        4. 需要记录nums1的索引，为了保存结果\n",
    "        5. 伪代码\n",
    "        6. 代数验证伪代码正确性\n",
    "        7. 翻译伪代码\n",
    "        8. 跑测试用例\n",
    "        \"\"\"\n",
    "        res = [-1] * len(nums1)\n",
    "        stack = []\n",
    "        for num in nums2:\n",
    "            while True:\n",
    "                if stack and num > nums1[stack[-1]]:\n",
    "                    index = stack.pop()\n",
    "                    res[index] = num\n",
    "                else:\n",
    "                    break\n",
    "            if num in nums1:\n",
    "                stack.append(nums1.index(num))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack=collections.deque()\n",
    "        res={}\n",
    "        for i in reversed(nums2):\n",
    "            while stack and i>=stack[-1]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                res[i]=stack[-1]\n",
    "            else :\n",
    "                res[i]=-1\n",
    "            stack.append(i)\n",
    "        return [res[i] for i in nums1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        i = 0\n",
    "        n_map = dict()\n",
    "        while i < len(nums2):\n",
    "            while s and s[-1] < nums2[i]:\n",
    "                n_map[s.pop()] = nums2[i]\n",
    "            s.append(nums2[i])\n",
    "            i += 1\n",
    "        while s:\n",
    "            n_map[s.pop()] = -1\n",
    "        return [n_map[x] for x in nums1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        result=[]\n",
    "        stack=[]\n",
    "        for i in nums2:\n",
    "            stack.append(i)\n",
    "        for i in nums1:\n",
    "            temp=[]\n",
    "            isFound=False\n",
    "            max_=-1\n",
    "            while len(stack)!=0 and not isFound:\n",
    "                top=stack.pop()\n",
    "                if top>i:\n",
    "                    max_=top\n",
    "                elif top==i:\n",
    "                    isFound=True\n",
    "                temp.append(top)\n",
    "            result.append(max_)\n",
    "            while len(temp)!=0:\n",
    "                stack.append(temp.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums1)\n",
    "        stack = [0]\n",
    "        for i in range(1,len(nums2)):\n",
    "            if nums2[i] <= nums2[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) != 0 and nums2[i] > nums2[stack[-1]]:\n",
    "                    if nums2[stack[-1]] in nums1:\n",
    "                        index = nums1.index(nums2[stack[-1]])\n",
    "                        res[index] = nums2[i]\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        dict1 = {}\n",
    "        for i in range(len(nums2)-1, -1, -1):\n",
    "            num = nums2[i]\n",
    "            while len(stack) != 0 and stack[-1] < num:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                dict1[num] = -1\n",
    "            else:\n",
    "                dict1[num] = stack[-1]\n",
    "            stack.append(num)\n",
    "        ans = []\n",
    "        for num in nums1:\n",
    "            ans.append(dict1[num])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        right = defaultdict(lambda:-1)\n",
    "        st = []\n",
    "        for x in nums2:\n",
    "            while st and st[-1]  < x:\n",
    "                right[st.pop()] = x\n",
    "            st.append(x)\n",
    "        return [right[i] for i in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        l = len(nums1)\n",
    "        ans = [-1] * l\n",
    "        for i in range(l):\n",
    "            tmp = nums1[i]\n",
    "            idx = nums2.index(tmp)\n",
    "            for num in nums2[idx + 1:]:\n",
    "                if num > tmp:\n",
    "                    ans[i] = num\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        nums1 = nums + nums\n",
    "        res = [-1] * len(nums)\n",
    "\n",
    "        for i, each in enumerate(nums):\n",
    "            for idx_ in range(i+1, len(nums1)):\n",
    "                if nums1[idx_] > each:\n",
    "                    res[i] = nums1[idx_]\n",
    "                    break\n",
    "\n",
    "        return res\n",
    "\n",
    "        # for i, each in enumerate(nums1):\n",
    "        #     idx = nums2.index(each)\n",
    "            \n",
    "        #     for idx_ in range(idx+1, len(nums2)):\n",
    "                \n",
    "        #         if nums2[idx_] > each:\n",
    "                    \n",
    "        #             res[i] = nums2[idx_]\n",
    "        #             break\n",
    "\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_double = nums + nums\n",
    "        stack = [0]\n",
    "        recoder = [0] * len(nums_double)\n",
    "\n",
    "        for i in range(1, len(nums_double)):\n",
    "            while len(stack) and nums_double[i] > nums_double[stack[-1]]:\n",
    "                recoder[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "\n",
    "        result = [-1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if recoder[i] != 0:\n",
    "                result[i] = nums_double[i + recoder[i]]\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        for i in range(len(nums)):\n",
    "            j=0\n",
    "            n=0\n",
    "            for k in range(i+1,len(nums)+i):\n",
    "                \n",
    "                \n",
    "                if k>=len(nums):\n",
    "                    k=j\n",
    "                    j=j+1\n",
    "                if nums[i]<nums[k] or k==i:\n",
    "                    if k==len(nums)+1:\n",
    "                        k==0\n",
    "                    ans.append(nums[k])\n",
    "                    n=1\n",
    "                    break\n",
    "                \n",
    "            if n==0:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            # idx = nums.index(i)\n",
    "            for j in range(i+1,len(nums)+i):\n",
    "                if nums[j%(len(nums))]>nums[i]:\n",
    "                    res[i] = nums[j%(len(nums))]\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        stk,res=[],[-1]*n\n",
    "        for i in range(n*2-1,-1,-1):\n",
    "            while stk and nums[i%n]>=stk[-1]:\n",
    "                stk.pop()\n",
    "            res[i%n]=stk[-1] if stk else -1\n",
    "            stk.append(nums[i%n])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        result = [-1]*len(nums)\n",
    "        stack.append(0)\n",
    "        for i in range(1, 2*len(nums)):\n",
    "            if nums[i%len(nums)] < nums[stack[-1]]:\n",
    "                stack.append(i%len(nums))\n",
    "            elif nums[i%len(nums)] == nums[stack[-1]]:\n",
    "                stack.append(i%len(nums))\n",
    "            elif nums[i%len(nums)] > nums[stack[-1]]:\n",
    "                while stack and nums[i%len(nums)] > nums[stack[-1]]:\n",
    "                    result[stack[-1]] = nums[i%len(nums)]\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            j = i+1\n",
    "            while j%len(nums) != i:  \n",
    "\n",
    "                if nums[j%len(nums)] > nums[i]:\n",
    "                    res[i] = nums[j%len(nums)]\n",
    "                    # print(i,j)\n",
    "                    break\n",
    "                j += 1\n",
    "        \n",
    "        # for j in range(len(nums)-1):\n",
    "        #     if nums[j] > nums[len(nums)-1]:\n",
    "        #         res[len(nums)-1] = nums[j]\n",
    "        #         break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)+i):\n",
    "                if nums[j%(len(nums))]>nums[i]:\n",
    "                    res[i] = nums[j%len(nums)]\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        N = len(nums)\n",
    "        res = [-1] * N\n",
    "        for i in range(N):\n",
    "            k = i + 1\n",
    "            cnt = N - 1 \n",
    "            while cnt > 0: \n",
    "                if k < N: \n",
    "                    if nums[k] > nums[i]: \n",
    "                        res[i] = nums[k]\n",
    "                        break    \n",
    "                else:\n",
    "                    if nums[k-N] > nums[i]: \n",
    "                        res[i] = nums[k-N]\n",
    "                        break\n",
    "                k += 1\n",
    "                cnt -= 1\n",
    "        return res\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        res = [-1 for _ in range(n)]\n",
    "        for i in range(n * 2 + 1, -1, -1):\n",
    "            while stack and nums[i % n] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            res[i % n] = stack[-1] if stack else -1 \n",
    "            stack.append(nums[i % n])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = [0]*n\n",
    "\n",
    "        if n == 0 or n == 1:\n",
    "            return [-1]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, i+n):\n",
    "                if nums[j%n] > nums[i]:\n",
    "                    res[i] = nums[j%n]\n",
    "                    break\n",
    "                else:\n",
    "                    res[i] = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(2*n-1, -1, -1):\n",
    "            while stack and nums[i%n] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            res[i%n] = stack[-1] if stack else -1\n",
    "            stack.append(nums[i%n])\n",
    "        return res\n",
    "        \n",
    "        # numsNew = nums * 2\n",
    "        # res = [-1] * len(numsNew)\n",
    "        # stack = []\n",
    "        # for i in range(len(numsNew)-1, -1, -1):\n",
    "        #     while stack and numsNew[i] >= stack[-1]:\n",
    "        #         stack.pop()\n",
    "        #     res[i] = stack[-1] if stack else -1\n",
    "        #     stack.append(numsNew[i])\n",
    "        # return res[:len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            j = (i+1)%len(nums)\n",
    "            while j!=i:\n",
    "                if nums[j]>nums[i]:\n",
    "                    result.append(nums[j])\n",
    "                    break\n",
    "                j=(j+1)%len(nums)\n",
    "            if j==i:\n",
    "                result.append(-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(2*len(nums)-1, -1, -1):\n",
    "            while stack and nums[i%len(nums)] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            res[i%len(nums)] = stack[-1] if stack else -1\n",
    "            stack.append(nums[i%len(nums)])\n",
    "        return res\n",
    "        \n",
    "        # numsNew = nums * 2\n",
    "        # res = [-1] * len(numsNew)\n",
    "        # stack = []\n",
    "        # for i in range(len(numsNew)-1, -1, -1):\n",
    "        #     while stack and numsNew[i] >= stack[-1]:\n",
    "        #         stack.pop()\n",
    "        #     res[i] = stack[-1] if stack else -1\n",
    "        #     stack.append(numsNew[i])\n",
    "        # return res[:len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n \n",
    "        maxn = max(nums)\n",
    "        stack = [maxn]\n",
    "        index = nums.index(maxn)\n",
    "\n",
    "        for i in range(index-1, -1, -1):\n",
    "            while nums[i] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            ans[i] = stack[-1]\n",
    "            stack.append(nums[i])\n",
    "        for i in range(n-1, index, -1):\n",
    "            while stack and nums[i] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            ans[i] = stack[-1] if stack else -1\n",
    "            stack.append(nums[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stk = deque()\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            while stk and nums[i] > stk[-1]:\n",
    "                stk.pop()\n",
    "            stk.append(nums[i])\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[i] >= stk[-1]:\n",
    "                stk.pop()\n",
    "            while stk and len(stk) >= n:\n",
    "                stk.popleft()\n",
    "            if stk:\n",
    "                res[i] = stk[-1]\n",
    "            stk.append(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        if n == 0 or n == 1:\n",
    "            return [-1]\n",
    "            \n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                for j in range(1,n):\n",
    "                    maxnum = max(nums[i],nums[j])\n",
    "                    if maxnum != nums[i]:\n",
    "                        res.append(maxnum)\n",
    "                        break\n",
    "                if maxnum == nums[i]:\n",
    "                    res.append(-1)\n",
    "            \n",
    "            elif i == n-1:\n",
    "                for j in range(n-1):\n",
    "                    maxnum = max(nums[i],nums[j])\n",
    "                    if maxnum != nums[i]:\n",
    "                        res.append(maxnum)\n",
    "                        break\n",
    "                if maxnum == nums[i]:\n",
    "                    res.append(-1)\n",
    "            \n",
    "            else:\n",
    "                for j in range(i+1,n):\n",
    "                    maxnum = max(nums[i],nums[j])\n",
    "                    if maxnum != nums[i]:\n",
    "                        res.append(maxnum)\n",
    "                        break\n",
    "                    elif j == n-1 and maxnum == nums[i]:\n",
    "                        for j in range(i):\n",
    "                            maxnum = max(nums[i],nums[j])\n",
    "                            if maxnum != nums[i]:\n",
    "                                res.append(maxnum)\n",
    "                                break\n",
    "                if maxnum == nums[i]:\n",
    "                    res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        res = [-1] * n\n",
    "\n",
    "        for i in range(2*n):\n",
    "            while stack and nums[stack[-1]] < nums[i%n]:\n",
    "                res[stack.pop()] = nums[i%n]\n",
    "            # if stack:\n",
    "            #     res[stack[-1]%n] = -1\n",
    "            stack.append(i%n)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        q = []\n",
    "        ans = [-1] * n\n",
    "        for i in range(n*2-1):\n",
    "            i = i % n\n",
    "            while q and nums[q[-1]] < nums[i]:\n",
    "                pos = q.pop()\n",
    "                ans[pos] = nums[i]\n",
    "            q.append(i)\n",
    "            # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(nums) * 2):\n",
    "            index = i % len(nums)\n",
    "            while stack and nums[index] > nums[stack[-1]]:\n",
    "                res[stack.pop()] = nums[index]\n",
    "            stack.append(index)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        nexts = [-1] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while (len(stack) != 0 and nums[i] > nums[stack[-1]]):\n",
    "                nexts[stack.pop()] = nums[i]\n",
    "            stack.append(i)\n",
    "        for i in range(len(nums)):\n",
    "            while (len(stack) != 0 and nums[i] > nums[stack[-1]]):\n",
    "                nexts[stack.pop()] = nums[i]\n",
    "        return nexts\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(2*len(nums)):\n",
    "            i = i % len(nums)\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                index = stack.pop()\n",
    "                res[index] = nums[i]\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stack = []\n",
    "\n",
    "        for i in range(2 * n - 1, -1, -1): # DOUBLE lenght of array to deal with loop\n",
    "            while stack and stack[-1] <= nums[i % n]: \n",
    "                stack.pop()\n",
    "            res[i % n] = -1 if not stack else stack[-1]\n",
    "            stack.append(nums[i % n])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = [-1] * n\n",
    "        stk = list()\n",
    "        for i in range(n * 2 - 1):\n",
    "            while stk and nums[stk[-1]] < nums[i % n]:\n",
    "                ret[stk.pop()] = nums[i%n]\n",
    "            stk.append(i % n)\n",
    "        return  ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        s = []\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(2*n - 1, -1, -1):\n",
    "            while s and s[-1] <= nums[i % n]:\n",
    "                s.pop()\n",
    "            if i < n:\n",
    "                res.append(s[-1] if s else -1)\n",
    "            s.append(nums[i % n])\n",
    "        res.reverse()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [-1]*len(nums)\n",
    "        l = len(nums)\n",
    "        for i in range(len(nums)*2):\n",
    "            while stack and nums[stack[-1]] < nums[i%l]:\n",
    "                index = stack.pop()\n",
    "                res[index] = nums[i%l]\n",
    "            stack.append(i%l)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "#         size = len(nums)\n",
    "\n",
    "#         if size == 1:\n",
    "#             return [-1]\n",
    "\n",
    "#         nums.extend(nums)\n",
    "#         res = [-1] * 2 * size\n",
    "#         stack = []\n",
    "\n",
    "#         for i in range(2 * size):\n",
    "#             while stack and nums[i] > nums[stack[-1]]:\n",
    "#                 idx = stack.pop()\n",
    "#                 res[idx] = nums[i]\n",
    "            \n",
    "#             stack.append(i)\n",
    "        \n",
    "#         return res[:size]\n",
    "            \n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        size = len(nums)\n",
    "\n",
    "        if size == 1:\n",
    "            return [-1]\n",
    "\n",
    "\n",
    "        res = [-1] * size\n",
    "        stack = []\n",
    "\n",
    "        for i in range(2 * size - 1):\n",
    "            while stack and nums[i % size] > nums[stack[-1]]:\n",
    "\n",
    "                res[stack.pop()] = nums[i % size]\n",
    "            \n",
    "            stack.append(i % size)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 5 4 3 2 1 5 4 3 2 \n",
    "        # 0 1 2 3 4 0 1 2 3\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(2 * n - 1):\n",
    "            while stack and nums[stack[-1]] < nums[i % n]:\n",
    "                ans[stack.pop()] = nums[i % n]\n",
    "            stack.append(i % n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, n: List[int]) -> List[int]:\n",
    "        l=[-1]*len(n)\n",
    "        for i in range(len(n)):\n",
    "            s=n[i+1:]+n[0:i]\n",
    "            for a in s:\n",
    "                if a>n[i]:\n",
    "                    l[i]=a\n",
    "                    break\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        res = [-1] * n\n",
    "        for i in range(2 * n - 1):\n",
    "            while stack and nums[stack[-1]] < nums[i % n]:\n",
    "                cur = stack.pop()\n",
    "                res[cur] = nums[i % n]\n",
    "            stack.append(i % n)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(nums)\n",
    "        # res = [-1] * n\n",
    "        # # stack = []\n",
    "        # # for i in range(2 * n - 1):\n",
    "        # #     while stack and nums[stack[-1]] < nums[i % n]:\n",
    "        # #         cur = stack.pop()\n",
    "        # #         res[cur] = nums[i % n]\n",
    "\n",
    "        # #     stack.append(i % n)\n",
    "\n",
    "        # # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        idx = nums.index(max(nums))\n",
    "        res = [-1] * n \n",
    "        stack = []\n",
    "        for i in range(idx+1, idx+1+n):\n",
    "            while(stack and nums[stack[-1]] < nums[i%n]):\n",
    "                res[stack.pop()] = nums[i%n]\n",
    "            stack.append(i%n)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 循环数组 要循环的找 \n",
    "        # 单调栈 递增 \n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)*2): # 至少遍历两次才能都找完 \n",
    "            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):\n",
    "                    # 如果栈非空且 当前元素（当前元素可以是第二次循环过来的 所以求模）大于栈顶\n",
    "                    # 处理 + 弹栈 \n",
    "                    res[stack[-1]] = nums[i%len(nums)] # 记录下一个更大的值作为答案\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums)) # 栈里记录位置 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 循环数组 要循环的找 \n",
    "        # 单调栈 递增 \n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)*2): # 至少遍历两次才能都找完 \n",
    "            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):\n",
    "                    # 如果栈非空且 当前元素（当前元素可以是第二次循环过来的 所以求模）大于栈顶\n",
    "                    # 处理 + 弹栈 \n",
    "                    res[stack[-1]] = nums[i%len(nums)] # 记录下一个\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [] \n",
    "        res = [-1] * n \n",
    "        for i in range(2*n):\n",
    "            while stack and nums[stack[-1] % n] < nums[i%n]:\n",
    "                res[stack[-1]%n] = nums[i%n]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(n * 2):\n",
    "            while stack and nums[i % n] > nums[stack[-1]]:\n",
    "                cur = stack.pop()\n",
    "                ans[cur] = nums[i % n]          \n",
    "            stack.append(i % n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stk = []\n",
    "        for i in range(len(nums)*2):\n",
    "            while stk and nums[i%len(nums)] > nums[stk[-1]]:\n",
    "                res[stk[-1]] = nums[i%len(nums)]\n",
    "                stk.pop()\n",
    "            stk.append(i%len(nums))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [] \n",
    "        res = [-1] * n \n",
    "        for i in range(2*n):\n",
    "            # while stack and nums[stack[-1] % n] < nums[i%n]:\n",
    "            #     res[stack[-1]%n] = nums[i%n]\n",
    "            #     stack.pop()\n",
    "            # stack.append(i)\n",
    "            while stack and nums[stack[-1]] < nums[i%n]:\n",
    "                res[stack[-1]] = nums[i%n] \n",
    "                stack.pop()\n",
    "            stack.append(i%n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        dp = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(nums)*2):\n",
    "            while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):\n",
    "                    dp[stack[-1]] = nums[i%len(nums)]\n",
    "                    stack.pop()\n",
    "            stack.append(i%len(nums))\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ans = [-1] * len(nums)*2\n",
    "\n",
    "        stk = []\n",
    "        nums += nums\n",
    "\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            while stk and stk[-1] <= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                ans[i] = stk[-1]\n",
    "            stk.append(nums[i])\n",
    "        \n",
    "        return ans[:len(nums)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1]*n \n",
    "        s = []\n",
    "        for i in range(2*n-1, -1, -1):\n",
    "            while s and s[-1] <= nums[i % n]:\n",
    "                s.pop()\n",
    "            if s:\n",
    "                res[i % n] = s[-1]\n",
    "            s.append(nums[i % n])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 维护一个单调递减栈\n",
    "        # 待入栈元素>栈顶元素，出栈\n",
    "        # 待入栈元素为所求\n",
    "        n=len(nums)\n",
    "        nums.extend(nums[:n-1])\n",
    "\n",
    "        stack = []\n",
    "        res= [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                res[stack.pop()] = nums[i]\n",
    "            stack.append(i)\n",
    "        return res[:n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        res = [-1] * len(nums)\n",
    "        nums = nums[::-1]\n",
    "        nums = nums + nums\n",
    "        \n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            while stack and stack[-1] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                if nums[i] < stack[-1]:\n",
    "                    res[i % n] = stack[-1]\n",
    "            stack.append(nums[i])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack,hashmap = [],{}\n",
    "        nums2 = nums + nums\n",
    "        result = [-1 for _ in nums2]\n",
    "        for i in range(len(nums2)):\n",
    "            while stack and nums2[stack[-1]] < nums2[i]:\n",
    "                result[stack.pop()] = nums2[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        q = deque([])\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        for i in range(2*n-1):\n",
    "            while q and nums[i%n] > nums[q[-1]]:\n",
    "                ans[q.pop()] = nums[i%n]\n",
    "            q.append(i%n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        cycle = nums * 2\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(2*n):\n",
    "            while stack and cycle[stack[-1]] < cycle[i]:\n",
    "                temp = stack.pop()\n",
    "                index = temp % n\n",
    "                ans[index] = cycle[i]\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        nums += nums\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                idx = stack.pop()\n",
    "                ans[idx] = nums[i]\n",
    "            stack.append(i)\n",
    "        return ans[:n//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        nums2=nums+nums\n",
    "        res=[-1]*len(nums2)\n",
    "        stack=[]\n",
    "        for i in range(len(nums2)):\n",
    "            while stack and nums2[stack[-1]]<nums2[i]:\n",
    "                index=stack.pop()\n",
    "                res[index]=nums2[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        return res[:len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        # 维护一个单调递减栈\n",
    "        # 待入栈元素>栈顶元素，出栈\n",
    "        # 待入栈元素为所求\n",
    "        n=len(nums)\n",
    "        nums.extend(nums[:n-1])\n",
    "\n",
    "        stack = []\n",
    "        res= [-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                res[stack.pop()] = nums[i]\n",
    "            stack.append(i)\n",
    "        return res[:n]\n",
    "\n",
    "# 不需要显性地将该循环数组「拉直」，而只需要在处理时对下标取模即可\n",
    "        # for i in range(n * 2 - 1):\n",
    "        #     while stk and nums[stk[-1]] < nums[i % n]:\n",
    "        #         ret[stk.pop()] = nums[i % n]\n",
    "        #     stk.append(i % n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums):\n",
    "        n=len(nums)\n",
    "        ans=[-1]*n\n",
    "        nums=nums*2\n",
    "        q=collections.deque()\n",
    "        for i in range(len(nums)):\n",
    "            if i==0:\n",
    "                q.appendleft(i)\n",
    "            elif i<n:\n",
    "                while len(q)!=0 and nums[i]>nums[q[0]]:\n",
    "                    ans[q[0]]=nums[i]\n",
    "                    q.popleft()\n",
    "                q.appendleft(i)\n",
    "            else:\n",
    "                while nums[i]>nums[q[0]]:\n",
    "                    ans[q[0]]=nums[i]\n",
    "                    q.popleft()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        #遍历两遍数组\n",
    "        stack=[]\n",
    "        res=[-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                cur=stack.pop()\n",
    "                res[cur]=nums[i]\n",
    "            stack.append(i)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                cur=stack.pop()\n",
    "                res[cur]=nums[i]\n",
    "        return res\n",
    "        '''\n",
    "        #直接将数组扩大两倍\n",
    "        stack=[]\n",
    "        nums=nums*2\n",
    "        res=[-1]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i]>nums[stack[-1]]:\n",
    "                cur=stack.pop()\n",
    "                res[cur]=nums[i]\n",
    "            stack.append(i)\n",
    "        return res[:len(nums)//2]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * 2*n\n",
    "        stk = []\n",
    "        double_nums = nums + nums\n",
    "\n",
    "        for i,num in enumerate(double_nums):\n",
    "            while stk and num > double_nums[stk[-1]]:\n",
    "                pop_index = stk.pop()\n",
    "                ans[pop_index] = num\n",
    "            \n",
    "            stk.append(i)\n",
    "        return ans[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums = nums + nums\n",
    "        right = [-1] *  (2*n) \n",
    "        stack = []\n",
    "        for i in range(2*n-1, -1, -1):\n",
    "            while len(stack) != 0 and nums[stack[-1]] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) != 0:\n",
    "                right[i] = nums[stack[-1]]\n",
    "            stack.append(i)\n",
    "        return right[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_2 = nums+nums\n",
    "        n = len(nums_2)\n",
    "        print(nums_2)\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #initialize stack\n",
    "        stack = []\n",
    "        #itereta nums 2 times\n",
    "        for i in range(n):\n",
    "            cur_num = nums_2[i]\n",
    "            while stack and cur_num>nums_2[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = cur_num\n",
    "\n",
    "            stack.append(i)\n",
    "            #print(stack)\n",
    "        half_n = int(n/2)\n",
    "        ans = ans[:half_n]\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_2 = nums+nums\n",
    "        n = len(nums_2)\n",
    "        print(nums_2)\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #initialize stack\n",
    "        stack = []\n",
    "        #itereta nums 2 times\n",
    "        for i in range(n):\n",
    "            cur_num = nums_2[i]\n",
    "            while stack and cur_num>nums_2[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = cur_num\n",
    "\n",
    "            stack.append(i)\n",
    "            #print(stack)\n",
    "        half_n = int(n/2)\n",
    "        ans = ans[:half_n]\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        nums += nums\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                idx = stack.pop()\n",
    "                ans[idx] = nums[i]\n",
    "            stack.append(i)\n",
    "        return ans[:n//2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack,hashmap = [],{}\n",
    "        nums2 = nums + nums\n",
    "        result = [-1 for _ in nums]\n",
    "        for i in range(len(nums2)):\n",
    "            while stack and nums2[stack[-1]] < nums2[i]:\n",
    "                index = stack.pop()\n",
    "                if index < len(result):\n",
    "                    result[index] = nums2[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        temp = nums[:]+nums[:]\n",
    "        n = len(nums)\n",
    "        ans = [-1 for _ in range(2*n)]\n",
    "        st = []\n",
    "        for index,num in enumerate(temp):\n",
    "            while st and num > temp[st[-1]]:\n",
    "                i = st.pop()\n",
    "                ans[i] = num\n",
    "            st.append(index)\n",
    "        st = []\n",
    "        return ans[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1 for _ in range(len(nums))]\n",
    "        nums.extend(nums)\n",
    "        stack = []\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if stack ==[]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if nums[stack[-1]]>= nums[i]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack!=[] and nums[stack[-1]]< nums[i]  :\n",
    "                        index = stack.pop(-1)%n\n",
    "                        res[index] = nums[i]\n",
    "                    stack.append(i)\n",
    "        # last = stack.pop(-1)\n",
    "        # res[last] = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        ret = [0] * l\n",
    "        stack = [(0, nums[0])] # (position, value) stack 剩下的是单调递减[包括相等的情况]\n",
    "        i = 1\n",
    "        second = False\n",
    "        while i<l:\n",
    "            v = nums[i]\n",
    "            # print(stack[-1])\n",
    "            while stack and v > stack[-1][1]:\n",
    "                k = stack.pop()\n",
    "                ret[k[0]] = v          \n",
    "            stack.append((i, v))      \n",
    "            i += 1\n",
    "            if not second and i >=l :\n",
    "                second = True\n",
    "                i = 0\n",
    "            if second and stack[0][-1] == stack[-1][-1]:\n",
    "                break\n",
    "        for i, v in stack:       \n",
    "            ret[i] = -1\n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l = nums + nums[:-1]\n",
    "        stack = []\n",
    "        re = [''] * len(nums)\n",
    "        for i in range(len(l)):\n",
    "            while stack and l[i] > l[stack[-1]]:\n",
    "                rei = stack.pop()\n",
    "                if rei < len(nums):\n",
    "                    re[rei] = l[i]    \n",
    "            stack.append(i)\n",
    "        re = [-1 if i == '' else i for i in re]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums_2 = nums+nums\n",
    "        n = len(nums_2)\n",
    "        print(nums_2)\n",
    "        ans = [-1 for i in range(n)]\n",
    "        #initialize stack\n",
    "        stack = []\n",
    "        #itereta nums 2 times\n",
    "        for i in range(n):\n",
    "            cur_num = nums_2[i]\n",
    "            #如果当前数比最新进stack的数字大\n",
    "            while stack and cur_num>nums_2[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = cur_num\n",
    "\n",
    "            stack.append(i)\n",
    "            #print(stack)\n",
    "        half_n = int(n/2)\n",
    "        ans = ans[:half_n]\n",
    "        print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        ret = [0] * l\n",
    "        stack = [(0, nums[0])] # (position, value) stack 剩下的是单调递减[包括相等的情况]\n",
    "        i = 1\n",
    "        second = False\n",
    "        while i<=l:\n",
    "            idx = i % l\n",
    "            v = nums[idx]\n",
    "            # print(stack[-1])\n",
    "            while stack and v > stack[-1][1]:\n",
    "                k = stack.pop()\n",
    "                ret[k[0]] = v          \n",
    "            stack.append((idx, v))      \n",
    "            i += 1\n",
    "            if not second and i > l:\n",
    "                second = True\n",
    "                i = 0\n",
    "            if second and  stack[0][-1] == stack[-1][-1]:\n",
    "                break\n",
    "        for i, v in stack:       \n",
    "            ret[i] = -1\n",
    "        \"\"\"\n",
    "        # 栈 v 已经是单调递减（或者完全相等的数）首位肯定没有更大的值\n",
    "        ret[stack[0][0]] = -1\n",
    "        for i, v in stack[1:]:\n",
    "            if v == stack[0][1]:\n",
    "                ret[i] = -1\n",
    "            else:\n",
    "                ret[i] = stack[0][1]\n",
    "        \"\"\"\n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        result = [-1] * len(nums)\n",
    "        stack = []\n",
    "        for index, value in enumerate(nums):\n",
    "            while stack and stack[-1][1] < value:\n",
    "                index_tmp, value_tmp = stack.pop()\n",
    "                result[index_tmp] = value\n",
    "            stack.append((index, value))\n",
    "        for index, value in enumerate(nums):\n",
    "            while stack and stack[-1][1] < value:\n",
    "                index_tmp, value_tmp = stack.pop()\n",
    "                result[index_tmp] = value\n",
    "            stack.append((index, value))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        n_nums= nums.copy()\n",
    "        nums.extend(n_nums)\n",
    "        nums = nums[:-1]\n",
    "\n",
    "        ans = [-1 for _ in range(n)]\n",
    "    \n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1, len(nums)):\n",
    "        #         if nums[j] > nums[i]:\n",
    "        #             ans[i] =nums[j]\n",
    "        #             break\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                ans[stack.pop()] = nums[i]\n",
    "            stack.append(i % n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        l=len(nums)\n",
    "        if l==1:\n",
    "            return [-1]\n",
    "        ans=[-1]*(l+l-1)\n",
    "        nums=nums+nums[0:l-1]\n",
    "        stk=[]\n",
    "        for i in range(l+l-1):\n",
    "            while stk and nums[stk[-1]]<nums[i]:\n",
    "                ans[stk.pop()]=nums[i]\n",
    "            stk.append(i)\n",
    "        return ans[:l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ans = [-1 for i in range(len(nums))]\n",
    "        stack = []\n",
    "        for index in range(len(nums) * 2 - 1):\n",
    "            while stack and nums[index % len(nums)] > stack[-1][1]:\n",
    "                ans[stack[-1][0]] = nums[index % len(nums)]\n",
    "                stack.pop()\n",
    "            stack.append((index % len(nums), nums[index % len(nums)]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def nextGreaterElements(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 5 1 2 3 6\n",
    "        stk=[]\n",
    "        n=len(nums)\n",
    "        ans=[-1]*n\n",
    "        for i,c in enumerate(nums+nums):\n",
    "            while stk and stk[-1][1]<c:\n",
    "                t=stk.pop()\n",
    "                if t[0]>=n: continue\n",
    "                ans[t[0]]=c\n",
    "            stk.append((i,c))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, a: List[int]) -> List[int]:\n",
    "        n = len(a)\n",
    "        a = a + a\n",
    "        q = deque()\n",
    "        ans = [-1] * n\n",
    "        for i in range(n+n-1, -1, -1):\n",
    "            while q and q[0][0] <= a[i]:\n",
    "                q.popleft()\n",
    "            if i < n and q and q[0][1] - i < n:\n",
    "                ans[i] = q[0][0]\n",
    "            q.appendleft((a[i],i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums2 = nums + nums\n",
    "        stack = [0]\n",
    "        ans = [0] * len(nums2)\n",
    "        for i, x in enumerate(nums2):\n",
    "            while stack and x > nums2[stack[-1]]:\n",
    "                ans[stack[-1]] = i\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        res = [nums2[x] if x!=0 else -1 for x in ans]\n",
    "        return res[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < 2*n:\n",
    "            cur = i % n\n",
    "            while stack and nums[cur] > stack[-1][0]:\n",
    "                val, index = stack.pop()\n",
    "                res[index] = nums[cur]\n",
    "            stack.append((nums[cur], cur))\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums)\n",
    "        stack = []\n",
    "        #print(list(range(len(nums)))+list(range(len(nums))))\n",
    "        for x, i in zip(nums+nums, list(range(len(nums)))+list(range(len(nums)))):\n",
    "\n",
    "            while stack and x > nums[stack[-1]]:\n",
    "                k = stack.pop(-1)\n",
    "                res[k] = x\n",
    "            stack.append(i)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stk = []\n",
    "        ans = [-1] * n\n",
    "        for i in range(2 * n - 1):\n",
    "            i = i % n\n",
    "            while stk and stk[-1][0] < nums[i]:\n",
    "                ans[stk[-1][1]] = nums[i]\n",
    "                stk.pop()\n",
    "            stk.append((nums[i], i))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ms,hashmap = [],dict()\n",
    "        for i,num in enumerate(nums):\n",
    "            while len(ms) > 0 and nums[ms[-1]] < num: hashmap[ms.pop()] = num\n",
    "            ms.append(i)\n",
    "        for i,num in enumerate(nums):\n",
    "            while len(ms) > 0 and nums[ms[-1]] < num: \n",
    "                if ms[-1] not in hashmap: hashmap[ms[-1]] = num\n",
    "                ms.pop()\n",
    "            ms.append(i)\n",
    "        return [hashmap.get(i,-1) for i in range(len(nums))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        stack=[]\n",
    "        dic={}\n",
    "        res=[]\n",
    "        nums=nums*2\n",
    "        for i in nums[::-1]:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            while stack and i>=stack[-1]:\n",
    "                stack.pop()\n",
    "            dic[i]=stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "            res.append(dic[i])\n",
    "        return res[::-1][:len(nums)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        doublenums = nums+nums \n",
    "        stack = []\n",
    "\n",
    "        ans = [-1]*(2*n)\n",
    "        for i in range(2*n):\n",
    "            if not stack:\n",
    "                stack.append((i,doublenums[i]))\n",
    "                continue \n",
    "            if stack[-1][1]>=doublenums[i]:\n",
    "                stack.append((i, doublenums[i]))\n",
    "                continue \n",
    "            else:\n",
    "                while stack and stack[-1][1]<doublenums[i]:\n",
    "                    index, x = stack[-1]\n",
    "    \n",
    "                    ans[index] = doublenums[i]\n",
    "                    stack.pop()\n",
    "\n",
    "                stack.append((i, doublenums[i]))\n",
    "               \n",
    "\n",
    "                \n",
    "        return ans[:n]             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        ns = nums * 2\n",
    "        ans, stack = [-1] * len(ns), []\n",
    "        for i in range(len(ns)):\n",
    "            current = ns[i]\n",
    "            while stack and stack[-1][0] < current:\n",
    "                ans[stack.pop()[1]] = current\n",
    "            stack.append((current, i))\n",
    "        return ans[:len(nums)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        nums1 = nums * 2\n",
    "        stack = []\n",
    "        ans = [-1] * len(nums)\n",
    "        for i in range(len(nums1)):\n",
    "            if not stack:\n",
    "                stack.append([i, nums1[i]])\n",
    "            else:\n",
    "                while stack and stack[-1][1] < nums1[i]:\n",
    "                    ans[stack[-1][0] % len(ans)] = nums1[i]\n",
    "                    stack.pop()\n",
    "                stack.append([i, nums1[i]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        decrease_stack = []\n",
    "        result_dict = {}\n",
    "        new_nums = nums + nums\n",
    "        for i in range(len(new_nums)):\n",
    "            while decrease_stack and new_nums[decrease_stack[-1]] < new_nums[i]:\n",
    "                t = decrease_stack.pop(-1)\n",
    "                if t < len(nums):\n",
    "                    result_dict[t] = (i - len(nums)) % len(nums)\n",
    "            decrease_stack.append(i)\n",
    "\n",
    "        while decrease_stack:\n",
    "            t = decrease_stack.pop(-1)\n",
    "            if t < len(nums) and t not in result_dict:\n",
    "                result_dict[t] = -1\n",
    "        result = []\n",
    "        for t in range(len(nums)):\n",
    "            if result_dict[t] > -1:\n",
    "                result.append(nums[result_dict[t]])\n",
    "            else:\n",
    "                result.append(-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        a=[]\n",
    "        z=max(nums)\n",
    "        c=[]\n",
    "        for b in nums:\n",
    "            if b!=z:\n",
    "                c.append(b)\n",
    "            else:\n",
    "                c.append(-1)\n",
    "        for b in range(len(nums)):\n",
    "            while a and nums[b]>a[-1][1]:\n",
    "                c[a[-1][0]]=nums[b]\n",
    "                a.pop()\n",
    "            a.append([b,nums[b]])\n",
    "        for b in range(len(nums)):\n",
    "            if not a:\n",
    "                break\n",
    "            while nums[b]>a[-1][1]:\n",
    "                c[a[-1][0]]=nums[b]\n",
    "                a.pop()\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElements(self, nums: List[int]) -> List[int]:\n",
    "        slow,fast=0,0\n",
    "        ret=[None]*len(nums)\n",
    "        while slow<len(nums):\n",
    "            if ret[slow]!=None:\n",
    "                slow+=1\n",
    "                continue\n",
    "            judge=0\n",
    "            fast=(slow+1)%len(nums)\n",
    "            stack=[]\n",
    "            while nums[fast]<=nums[slow]:\n",
    "                if fast==slow and judge==1:\n",
    "                    break\n",
    "                judge=1\n",
    "                while len(stack)!=0 and nums[fast]>stack[-1][0]:\n",
    "                    ret[stack[-1][1]]=nums[fast]\n",
    "                    stack.pop()\n",
    "                stack.append([nums[fast],fast])\n",
    "                fast=(fast+1)%len(nums)\n",
    "            if fast==slow and judge==1:\n",
    "                ret[slow]=-1\n",
    "            else:\n",
    "                ret[slow]=nums[fast]\n",
    "            while len(stack)!=0:\n",
    "                val,i=stack.pop()\n",
    "                if val==nums[slow]:\n",
    "                    continue\n",
    "                ret[i]=nums[fast]\n",
    "            slow=fast\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=list(str(n))\n",
    "        i=len(nums)-2\n",
    "        while i>=0 and nums[i]>=nums[i+1]:\n",
    "            i-=1\n",
    "        if i<0:\n",
    "            return -1\n",
    "        j=len(nums)-1\n",
    "        while j>=0 and nums[i]>=nums[j]:\n",
    "            j-=1\n",
    "        nums[i],nums[j]=nums[j],nums[i]\n",
    "        nums[i+1:]=nums[i+1:][::-1]\n",
    "        res=int(''.join(nums))\n",
    "        return res if res<2**31 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=list(str(n))\n",
    "        daoxu=True\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i]<nums[i+1]:\n",
    "                daoxu=False\n",
    "                break\n",
    "        if daoxu:\n",
    "            return -1\n",
    "        \n",
    "        for i in range(len(nums)-1,0,-1):\n",
    "            if nums[i]>nums[i-1]:\n",
    "                break\n",
    "        for j in range(len(nums)-1,0,-1):\n",
    "            if nums[i-1]<nums[j]:\n",
    "                nums[i-1],nums[j]=nums[j],nums[i-1]\n",
    "                tmp=[]\n",
    "                for item in nums[i:]:\n",
    "                    tmp.append(item)\n",
    "                tmp.sort()\n",
    "                nums[i:]=tmp\n",
    "                break\n",
    "        result=int(nums[0])\n",
    "        for item in nums[1:]:\n",
    "            result=result*10+int(item)\n",
    "        if result>=1 and result<=2**31-1:\n",
    "            return result\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        s = [ch for ch in str(n)[::-1]] # 得到低位到高位的数组\n",
    "\n",
    "        idx = -1\n",
    "        for i, x in enumerate(s):\n",
    "            if i and x < s[i-1]:\n",
    "                idx = i\n",
    "                break\n",
    "        \n",
    "        if idx == -1:   return -1   # 说明数字从低到高是 非严格递增的 \n",
    "\n",
    "        for i in range(idx):\n",
    "            if s[i] > s[idx]:\n",
    "                j = i\n",
    "                break   # 找到第一个就要及时退出\n",
    "\n",
    "        s[j], s[idx] = s[idx], s[j] # 交换\n",
    "        left, right = 0, idx-1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        ans = int(\"\".join(s[::-1]))\n",
    "        print(ans)\n",
    "        return ans if ans < (1 << 31) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "要让下一个更大元素尽可能地小, 那么从低位开始向高位找是最好的.\n",
    "如果从低位开始向高位遍历所有数字是 非严格递增 的, 那么无法通过组合得到下一个更大元素\n",
    "\n",
    "在找到 第一个递减的下标 idx 时, 从低位开始遍历找到第一个大于 s[idx] 的数字 s[j],\n",
    "交换 s[idx] 和 s[j] 后, 因为需要使下一个更大元素尽可能小, 还需要对 s[idx+1:] 进行反转;\n",
    "因为在倒序遍历时, s[idx+1:] 符合 非严格递减(倒过来是 非严格递增), \n",
    "那么需要通过反转使 s[idx+1:] 符合 非严格递增\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        s = [ch for ch in str(n)[::-1]]\n",
    "\n",
    "        idx = -1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] < s[i-1]:\n",
    "                idx = i\n",
    "                break\n",
    "        \n",
    "        if idx == -1:   # 从低位开始向高位都是 非严格递增 \n",
    "            return -1\n",
    "\n",
    "        for i in range(idx):\n",
    "            if s[i] > s[idx]:\n",
    "                j = i\n",
    "                break\n",
    "\n",
    "        s[idx], s[j] = s[j], s[idx]\n",
    "        left, right = 0, idx-1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        # 题目要求返回一个32位整数, 因此当 ans < (1 << 31) 才能返回 ans, 否则返回 -1\n",
    "        ans = int(\"\".join(s[::-1]))\n",
    "        return ans if ans < 1 << 31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 本质是全排列中下一个排列\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "        # 重排序\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        \n",
    "        # 找到第一个右边数字比左边数字小的位置\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        \n",
    "        if i < 0:\n",
    "            return -1  # 不存在更大的重新排列\n",
    "        \n",
    "        j = len(nums) - 1\n",
    "        \n",
    "        # 找到最小的右边较大数字\n",
    "        while j >= 0 and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        \n",
    "        nums[i], nums[j] = nums[j], nums[i]  # 交换两个数字\n",
    "        \n",
    "        # 对交换位置后的部分进行排序，确保是最小的重新排列\n",
    "        nums[i + 1:] = sorted(nums[i + 1:])\n",
    "        \n",
    "        result = int(''.join(nums))\n",
    "        \n",
    "        return result if result <= 2**31 - 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        # def insert(seq, val, val1):\n",
    "        #     # seq 已是顺序\n",
    "        #     seq.remove(val1)\n",
    "        #     if not seq:\n",
    "        #         return [val]\n",
    "            \n",
    "        #     flag = False\n",
    "        #     for i, num in enumerate(seq):\n",
    "        #         if not flag and val < num:\n",
    "        #             flag  = True\n",
    "        #             seq = seq[:i] + [val] + seq[i:]\n",
    "        #     if not flag:\n",
    "        #         seq.append(val)\n",
    "        #     return seq\n",
    "\n",
    "        # 本质是求下一个排列\n",
    "        nums = list(str(n))\n",
    "        size = len(nums)\n",
    "        # i = size - 2\n",
    "        #1. 从右往左遍历找到第一个下降的元素索引i\n",
    "        s = [nums.pop()]\n",
    "        while nums:\n",
    "            if nums[-1] < s[-1]:\n",
    "                break\n",
    "            else:\n",
    "                s.append(nums.pop())\n",
    "\n",
    "        if not nums: # 说明数组已逆序，无下一个更大的排列了\n",
    "            return -1\n",
    "\n",
    "        #2.将元素a[i]和其右侧比他大的最小元素交换, 并将a[i]插入有序的s中\n",
    "        # temp = nums[-1]\n",
    "        i = 0\n",
    "        print(s, nums)\n",
    "        while i < len(s):\n",
    "            # print(i)\n",
    "            if s[i] > nums[-1]:\n",
    "                nums[-1], s[i] = s[i], nums[-1]\n",
    "                # s[i] = temp\n",
    "                break\n",
    "\n",
    "            i += 1\n",
    "        \n",
    "        res = nums + s\n",
    "        res = int(''.join(res))\n",
    "        #top1 = nums.pop()\n",
    "        # for i in range(1, len(s)+1):\n",
    "        #     res = nums.copy()\n",
    "        #     #print(nums, s, top1)\n",
    "        #     top2 = s[-i] \n",
    "        #     res.append(top2)\n",
    "\n",
    "        #     res = res + insert(s.copy(), top1, top2)\n",
    "        # #res = nums[:i-1] + [nums[i+1]] + ([nums[i]].extend(nums[i+2:])).sort()\n",
    "        #     res = int(''.join(res))\n",
    "        #     #print(res)\n",
    "        #     if res <= 2 **31-1:\n",
    "        #         break\n",
    "\n",
    "        return res if res <= 2**31-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=list(str(n))\n",
    "        \n",
    "        n=len(nums)\n",
    "        if n<=1:\n",
    "            return -1\n",
    "        a=n-2\n",
    "        while a>=0 and nums[a]>=nums[a+1]:\n",
    "            a-=1\n",
    "        if a<0:\n",
    "            return -1\n",
    "        b=n-1\n",
    "        while b>=0 and nums[a]>=nums[b]:\n",
    "            b-=1\n",
    "        nums[a],nums[b]=nums[b],nums[a]\n",
    "        nums[a+1:]=sorted(nums[a+1:])\n",
    "        number_new=int(''.join(nums))\n",
    "        return number_new if number_new<2**31 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "\n",
    "        st = list(str(n))\n",
    "        \n",
    "        #倒序 找升序\n",
    "        i = len(st)-2\n",
    "        while i>=0 and st[i]>=st[i+1]:\n",
    "            i -= 1\n",
    "\n",
    "        if i >= 0:\n",
    "            j = len(st) - 1\n",
    "            while j > i and st[j]<=st[i]:\n",
    "                j -= 1\n",
    "            st[i],st[j] = st[j],st[i]\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        left = i+1\n",
    "        right = len(st)-1\n",
    "        while(left<right):\n",
    "            st[left],st[right] = st[right],st[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        \n",
    "        ans = int(''.join(st))\n",
    "        return ans if ans <2**31 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        if n >=2147483486:return -1\n",
    "        nums = list(str(n))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = int(nums[i])\n",
    "        \n",
    "        index = len(nums)-2\n",
    "\n",
    "        while index>=0 and nums[index]>= nums[index+1]:\n",
    "            index-=1\n",
    "        if index>=0:\n",
    "            j = len(nums)-1\n",
    "            while j>=0 and nums[j]<=nums[index]:\n",
    "                j-=1\n",
    "            nums[j], nums[index] = nums[index], nums[j]\n",
    "            \n",
    "            left = index+1\n",
    "            right = len(nums)-1\n",
    "            while left<right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left+=1\n",
    "                right-=1\n",
    "            sums = 0\n",
    "            for i in nums:\n",
    "                sums = sums* 10+i\n",
    "            if sums >=4294967296:return -1\n",
    "            return sums\n",
    "        else:\n",
    "            return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=list(str(n))\n",
    "        i=len(nums)-2\n",
    "        while i>=0 and nums[i]>=nums[i+1]:\n",
    "            i-=1\n",
    "        if i<0:\n",
    "            return -1\n",
    "        j=len(nums)-1\n",
    "        while j>=0 and nums[i]>=nums[j]:\n",
    "            j-=1\n",
    "        nums[i],nums[j]=nums[j],nums[i]\n",
    "        nums[i+1:]=nums[i+1:][::-1]\n",
    "        ans=int(''.join(nums))\n",
    "        return ans if ans <2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        n_str = list(str(n))\n",
    "        length= len(n_str)\n",
    "        index = length - 2\n",
    "        while index >= 0:\n",
    "            if n_str[index] < n_str[index + 1]:\n",
    "                break\n",
    "            index -=1\n",
    "        if index == -1:\n",
    "            return -1\n",
    "        k = length - 1\n",
    "        while k > index:\n",
    "            if n_str[k] > n_str[index]:\n",
    "                break\n",
    "            k -= 1\n",
    "        if not k:\n",
    "            return -1\n",
    "        n_str[index], n_str[k] = n_str[k], n_str[index]\n",
    "        n_str[index + 1:] = n_str[index+1:][::-1]\n",
    "        res = int(''.join(n_str))\n",
    "        if res < 2**31:\n",
    "            return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        l = len(nums)\n",
    "        i = l - 2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "        j = l - 1\n",
    "        while j >= 0 and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1:] = reversed(nums[i+1:])\n",
    "        res =  int(\"\".join(nums)) \n",
    "        return res if res <= 2**31-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        x, cnt = n, 1\n",
    "        while x>=10 and x//10 %10 >= x%10:\n",
    "            cnt+=1\n",
    "            x //= 10\n",
    "        x //= 10\n",
    "        if x==0: return -1\n",
    "\n",
    "        targetdigit = x % 10\n",
    "        x2, cnt2 = n, 0\n",
    "        while x2 % 10 <= targetdigit:\n",
    "            x2 //= 10\n",
    "            cnt2 +=1\n",
    "        x += x2 % 10 - targetdigit\n",
    "\n",
    "        INF = 2**31-1\n",
    "\n",
    "        for i in range(cnt):\n",
    "            d = n%10 if i!= cnt2 else targetdigit\n",
    "            x = x*10+d\n",
    "            if x>INF: return -1\n",
    "            n//=10\n",
    "        return x \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        i = n -2\n",
    "\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = n - 1\n",
    "            while j >= i and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        left, right = i+1 , n-1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        \n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        tp = []\n",
    "        while n > 0:\n",
    "            tp.append(n%10)\n",
    "            n = n//10\n",
    "       \n",
    "        i = 1\n",
    "        \n",
    "        while i < len(tp):\n",
    "            if tp[i] < tp[i-1]: break\n",
    "            i += 1\n",
    "        if i == len(tp): return -1\n",
    "        nxt_key = i-1\n",
    "        for j in range(i):\n",
    "            if tp[j] > tp[i]: break\n",
    "        temp = tp[i]\n",
    "        tp[i] = tp[j]\n",
    "        tp[j] = temp\n",
    "        tp[:i] = tp[:i][::-1]\n",
    "        \n",
    "\n",
    "       \n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(tp)):\n",
    "            res += tp[i]*10**(i)\n",
    "        return res if res <= 2**31-1 else -1\n",
    "            \n",
    "           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = []\n",
    "        stack = []\n",
    "        res = -1\n",
    "        while (n != 0):\n",
    "            nums.append(n%10)\n",
    "            n //= 10\n",
    "        nums = list(reversed(nums))\n",
    "        for i in reversed(range(len(nums))):\n",
    "            val = nums[i]\n",
    "            if (len(stack) != 0 and val < stack[-1]):\n",
    "                for j in range(len(stack)):\n",
    "                    if (stack[j] > val):\n",
    "                        nums[i] = stack[j]\n",
    "                        stack[j] = val\n",
    "                        # union two list\n",
    "                        stack.sort()\n",
    "                        nums[-len(stack):] = stack\n",
    "                        res = 0\n",
    "                        for i in range(len(nums)):\n",
    "                            res = res * 10 + nums[i]\n",
    "                        if (res > 2**31 - 1):\n",
    "                            res = -1\n",
    "                        break\n",
    "                break\n",
    "            stack.append(val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        stack = []\n",
    "        for nn in n:\n",
    "            stack.append(nn)\n",
    "        l = len(stack)\n",
    "        i= l-1\n",
    "        while i >0 and int(stack[i])<=int(stack[i-1]):\n",
    "            i-=1\n",
    "        if i==0:\n",
    "            return -1\n",
    "        small = i-1\n",
    "        i = l-1\n",
    "        while i>small and int(stack[i])<=int(stack[small]):\n",
    "            i-=1\n",
    "        stack[i],stack[small] =stack[small],stack[i]\n",
    "        left = small+1\n",
    "        right = l-1\n",
    "        while left<right :\n",
    "            stack[left],stack[right] = stack[right],stack[left]\n",
    "            left += 1\n",
    "            right -=1\n",
    "        n = int(''.join(stack))\n",
    "        print(n)\n",
    "        return n if n <= 2**31-1 else -1  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        m = len(nums)\n",
    "        i = m-2\n",
    "\n",
    "        while i>=0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i<0:\n",
    "            return -1\n",
    "\n",
    "        j = m-1\n",
    "        while j>=i and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1:] = nums[i+1:][::-1]\n",
    "        ans = int(\"\".join(nums))\n",
    "        return ans if ans < 2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        m = len(nums)\n",
    "        i = m-2\n",
    "\n",
    "        while i>=0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i<0:\n",
    "            return -1\n",
    "\n",
    "        j = m-1\n",
    "        while j>=0 and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1:] = nums[i+1:][::-1]\n",
    "        ans = int(\"\".join(nums))\n",
    "        return ans if ans < 2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        l = []\n",
    "        for i in str(n):\n",
    "            l.append(i)\n",
    "        idx = -1\n",
    "        ii = -1\n",
    "        target = -1\n",
    "        for i in range(len(l)-1,0,-1):\n",
    "            if int(l[i])>int(l[i-1]):\n",
    "                idx = i-1\n",
    "                ii = i\n",
    "                target = int(l[i])\n",
    "                for j in range(i+1,len(l)):\n",
    "                    if int(l[idx])<int(l[j])<target:\n",
    "                        target = int(l[j])\n",
    "                        ii = j\n",
    "                break\n",
    "        l[idx],l[ii] = l[ii],l[idx]\n",
    "\n",
    "        if idx == -1:\n",
    "            return -1\n",
    "\n",
    "        ll = sorted(l[idx+1:])\n",
    "        l[idx+1:] = ll\n",
    "\n",
    "\n",
    "        \n",
    "        a = int(''.join(l))\n",
    "        \n",
    "        return a if 1<=a<2**31 else -1\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=list(str(n))\n",
    "        i=len(nums)-2\n",
    "        while i>=0 and nums[i]>=nums[i+1]:\n",
    "            i-=1\n",
    "        if i<0:\n",
    "            return -1\n",
    "        \n",
    "        j=len(nums)-1\n",
    "        while j>=0 and nums[i]>=nums[j]:\n",
    "            j-=1\n",
    "        nums[i],nums[j]=nums[j],nums[i]\n",
    "        nums[i+1:]=nums[i+1:][::-1]\n",
    "        ans=int(''.join(nums))\n",
    "        return ans if ans<2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "要让下一个更大元素尽可能地小, 那么从低位开始向高位找是最好的.\n",
    "如果从低位开始向高位遍历所有数字是 非严格递增 的, 那么无法通过组合得到下一个更大元素\n",
    "\n",
    "在找到 第一个递减的下标 idx 时, 从低位开始遍历找到第一个大于 s[idx] 的数字 s[j],\n",
    "交换 s[idx] 和 s[j] 后, 因为需要使下一个更大元素尽可能小, 还需要对 s[idx+1:] 进行反转;\n",
    "因为在倒序遍历时, s[idx+1:] 符合 非严格递减(倒过来是 非严格递增), \n",
    "那么需要通过反转使 s[idx+1:] 符合 非严格递增\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        s = [ch for ch in str(n)[::-1]]\n",
    "\n",
    "        idx = -1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] < s[i-1]:\n",
    "                idx = i\n",
    "                break\n",
    "        \n",
    "        if idx == -1:   # 从低位开始向高位都是 非严格递增 \n",
    "            return -1\n",
    "\n",
    "        for i in range(idx):\n",
    "            if s[i] > s[idx]:\n",
    "                j = i\n",
    "                break\n",
    "\n",
    "        s[idx], s[j] = s[j], s[idx]\n",
    "        left, right = 0, idx-1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        ans = int(\"\".join(s[::-1]))\n",
    "        return ans if ans < 1 << 31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        num = []\n",
    "        while n:\n",
    "            num.append(n%10)\n",
    "            n = n // 10\n",
    "        \n",
    "        def convert(num):\n",
    "            # print(num)\n",
    "            res = 0\n",
    "            for n in num:\n",
    "                res = res * 10 + n\n",
    "                # print(res)\n",
    "                if res > 2**31 -1:\n",
    "                    return -1\n",
    "            return res\n",
    "\n",
    "        for i in range(len(num)-1):\n",
    "            if num[i+1] < num[i]:\n",
    "                j = i-1\n",
    "                while j >= 0 and num[j] > num[i+1]:\n",
    "                    j -= 1\n",
    "                num[j+1], num[i+1] = num[i+1], num[j+1]\n",
    "                l, r = 0, i\n",
    "                # print(num)\n",
    "                while l < r:\n",
    "                    num[l], num[r] = num[r], num[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                # print(num)\n",
    "                return convert(num[::-1])\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 本质是全排列中下一个排列\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        while j >= i and nums[i] >= nums[j]:   # 因为i右侧是降序排列，所以找到第一个大于i的就行就是最小的较大值\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "        # 重排序\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        lis = list(str(n))\n",
    "        res = n\n",
    "        for i in reversed(range(len(lis))):\n",
    "            if i == len(lis) - 1:\n",
    "                min_num = int(lis[i])\n",
    "                min_index = i\n",
    "            elif int(lis[i]) < int(lis[i + 1]):\n",
    "                for j in reversed(range(i + 1, len(lis))):\n",
    "                    if int(lis[j]) > int(lis[i]):\n",
    "                        lis[i], lis[j] = lis[j], lis[i]\n",
    "                        break\n",
    "                res = int(\"\".join(lis[:i + 1] + sorted(lis[i + 1:])))\n",
    "                break\n",
    "        if res == n or res >= 2 ** 31:\n",
    "            return -1\n",
    "        else:\n",
    "            return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        a = list(str(n))\n",
    "        for i in range(len(a)):\n",
    "            a[i] = int(a[i])\n",
    "        idx1 = -1\n",
    "        idx2 = -1\n",
    "        for i in range(len(a)-2, -1, -1):\n",
    "            # print(i)\n",
    "            if a[i] < a[i+1]:\n",
    "                idx1 = i\n",
    "                break\n",
    "        for i in range(len(a)-1, -1, -1):\n",
    "            # print('a:', a[i], a[idx1])\n",
    "            if a[i] > a[idx1]:\n",
    "                idx2 = i\n",
    "                break\n",
    "        if idx1 == -1:\n",
    "            return idx1\n",
    "        else:\n",
    "            num = a[idx1]\n",
    "            a[idx1] = a[idx2]\n",
    "            a[idx2] = num\n",
    "            a1 = a[idx1+1:]\n",
    "            a1.sort()\n",
    "            a[idx1+1:] = a1\n",
    "            s = \"\".join(str(x) for x in a)\n",
    "            ans = int(s)\n",
    "            if ans > 2 ** 31 - 1:\n",
    "                return -1\n",
    "            else:\n",
    "                return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        n_list = list(str(n))\n",
    "        n_len = len(n_list)\n",
    "        l = n_len - 1\n",
    "        while l > 0 and n_list[l] <= n_list[l-1]:\n",
    "            l -= 1\n",
    "        if l == 0:\n",
    "            return -1\n",
    "        if l == n_len - 1:\n",
    "            n_list[l-1], n_list[l] = n_list[l], n_list[l-1]\n",
    "        else:\n",
    "            left = l\n",
    "            right = n_len\n",
    "            nu = n_list[l-1]\n",
    "            while left < right - 1:\n",
    "                mid = (left + right) // 2\n",
    "                if n_list[mid] > nu:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid \n",
    "            n_list[l-1], n_list[left] = n_list[left], n_list[l-1]\n",
    "            n_list[l:] = reversed(n_list[l:])\n",
    "        res = int(''.join(n_list))\n",
    "        return res if res <= 2**31-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        i = n -2\n",
    "\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = n - 1\n",
    "            while j >= i and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        left, right = i+1 , n-1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        \n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        stack = []\n",
    "        digi = []\n",
    "        n_s = str(n)\n",
    "        res = 0\n",
    "        for symbol in n_s:\n",
    "            digi.append(int(symbol))\n",
    "        for i in reversed(range(len(digi))):\n",
    "            val = digi[i]\n",
    "            if (len(stack) != 0 and digi[i] < stack[-1]):\n",
    "                for j in range(len(stack)):\n",
    "                    if (stack[j] > val):\n",
    "                        digi[i] = stack[j]\n",
    "                        stack[j] = val\n",
    "                        break\n",
    "                stack.sort()\n",
    "                m = len(stack)\n",
    "                digi[-m:] = stack\n",
    "                print(digi)\n",
    "                for i in range(len(digi)):\n",
    "                    res = res * 10 + digi[i]\n",
    "                if (res >= 2**31):\n",
    "                    res = -1\n",
    "                break\n",
    "            stack.append(digi[i])\n",
    "        if (res == 0):\n",
    "            res = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        num = list(str(n))\n",
    "        num = [int(l) for l in num]\n",
    "        k = -1\n",
    "        tmp = None\n",
    "        for i in range(1,len(num)):\n",
    "            if num[i] > num[i-1]:\n",
    "                k = i-1\n",
    "        if k == -1: return -1\n",
    "        \n",
    "        for i in range(k,len(num)):\n",
    "            if num[i] > num[k]:\n",
    "                if tmp == None or num[i] < num[tmp]:\n",
    "                    tmp = i\n",
    "        num[k], num[tmp] = num[tmp], num[k]\n",
    "        num[k+1:] = sorted(num[k+1:])\n",
    "\n",
    "        # print(k,tmp,num)\n",
    "        ans = 0\n",
    "        k = 1\n",
    "        for i in range(len(num)-1,-1,-1):\n",
    "            ans += k*num[i]\n",
    "            k*= 10\n",
    "        # print(2**31,ans)\n",
    "        if ans >= 2**31: return -1\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i] , nums[j] = nums[j] , nums[i]\n",
    "        nums[i+1:] = nums[i+1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        # def lt556(n):\n",
    "        #     ll=list(str(n))\n",
    "        #     for i in range(len(ll)-2,-1,-1):\n",
    "        #         if ll[i]<ll[i+1]:\n",
    "        #             ll[i],ll[i+1]=ll[i+1],ll[i]\n",
    "        #             temp=ll[i+1:]\n",
    "        #             temp.sort()\n",
    "        #             ll=ll[:i+1]+temp\n",
    "        #             return int(''.join(ll))\n",
    "        #     return -1\n",
    "        # return lt556(n)\n",
    "\n",
    "        def lt556(n):\n",
    "            ll=list(str(n))\n",
    "            for i in range(len(ll)-2,-1,-1):\n",
    "                if ll[i]<ll[i+1]:\n",
    "                    temp=ll[i:]\n",
    "                    temp.sort()\n",
    "                    for k in range(len(temp)):\n",
    "                        if temp[k]>ll[i]:\n",
    "                            temp=[temp[k]]+temp[:k]+temp[k+1:]\n",
    "                            break\n",
    "                    ll=ll[:i]+temp\n",
    "                    res=int(''.join(ll))\n",
    "                    return res if res<=(2**31-1) else -1\n",
    "            return -1\n",
    "        return lt556(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=[int(w) for w in str(n)]\n",
    "        n=len(nums)\n",
    "        cnt=Counter()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            cnt[nums[i]]+=1\n",
    "            if nums[i]<max(cnt):\n",
    "                tmp=sorted(cnt.keys())\n",
    "                tar=tmp[bisect_right(tmp,nums[i])]\n",
    "                nums[i]=tar\n",
    "                cnt[tar]-=1\n",
    "                nums=nums[:i+1]\n",
    "                for key in tmp:\n",
    "                    nums+=[key]*cnt[key]\n",
    "\n",
    "                new_n=0\n",
    "                for num in nums:\n",
    "                    new_n*=10\n",
    "                    new_n+=num\n",
    "                if new_n >2**31-1:\n",
    "                    return -1\n",
    "                return new_n \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        flag = 0\n",
    "        for i in range(len(s)-1, 0, -1):\n",
    "            if s[i] > s[i-1]:\n",
    "                left = i-1\n",
    "                flag = 1\n",
    "                break\n",
    "        if not flag:\n",
    "            return -1\n",
    "        for j in range(len(s)-1, left, -1):\n",
    "            if s[j] > s[left]:\n",
    "                right = j\n",
    "                break\n",
    "        s[left], s[right] = s[right], s[left]\n",
    "        for k in range(left+1, (len(s)+left+1)//2):\n",
    "            s[k], s[len(s)+left-k] = s[len(s)+left-k], s[k]\n",
    "        ans = int(\"\".join(s))\n",
    "        return ans if ans <= 2**31-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = [int(ch) for ch in str(n)[::-1]]\n",
    "        print(nums)\n",
    "        n = len(nums)\n",
    "\n",
    "        idx = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if i and x < nums[i - 1]:\n",
    "                idx = i # 第一个递减的数的下标\n",
    "                break\n",
    "\n",
    "        if idx == -1:\n",
    "            return -1\n",
    "\n",
    "        for i in range(0, i):\n",
    "            if nums[i] > nums[idx]: # 第一个大于 nums[idx] 的数\n",
    "                nums[idx], nums[i] = nums[i], nums[idx]\n",
    "                break\n",
    "\n",
    "        l, r = 0, idx - 1\n",
    "        while l < r:\n",
    "            nums[l], nums[r] = nums[r], nums[l]\n",
    "            l, r = l + 1, r - 1\n",
    "\n",
    "        ans = int(\"\".join(str(ch) for ch in nums[::-1]))\n",
    "        return -1 if ans >= 2 ** 31 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        if n < 10:\n",
    "            return -1\n",
    "        temp = [0] * 10 # 0-9\n",
    "        while n:\n",
    "            x = n % 10\n",
    "            n = n // 10\n",
    "            temp[x] += 1\n",
    "            flag = False\n",
    "            for i in range(x+1, 10):\n",
    "                if temp[i]:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                t = str(i)\n",
    "                temp[i] -= 1\n",
    "                for i,k in enumerate(temp):\n",
    "                    if k >0:\n",
    "                        t += str(i)*k\n",
    "                result = int(str(n)+t)\n",
    "                if result > 2147483647:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return result\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "\n",
    "        # 123 后面位数要比前面位数大，才满足要求\n",
    "        # 从个位开始，倒序遍历\n",
    "        # 符合条件的最小整数\n",
    "\n",
    "        # 遍历n,找元素后面比他大的最小值\n",
    "        s = list(str(n))\n",
    "        m = len(s)\n",
    "\n",
    "        j = -1\n",
    "        stack = []   # 单调递增,存的是s索引\n",
    "       \n",
    "        for i in range(m-1, -1, -1):  \n",
    "\n",
    "            while stack and s[i] < s[stack[-1]]:\n",
    "                j = stack[-1]\n",
    "                stack.pop()\n",
    "                \n",
    "            if j != -1:   \n",
    "                s[i], s[j] = s[j], s[i]\n",
    "                # 找后面最小的\n",
    "                s2 = s[:i+1] + sorted(s[i+1:])\n",
    "                res = int(''.join(s2))\n",
    "                if res < 2 ** 31:\n",
    "                    return res \n",
    "                else:\n",
    "                    return -1\n",
    "            stack.append(i)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "\n",
    "        nums = list(str(n))\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        i = n - 2\n",
    "\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        \n",
    "        if i < 0: return -1\n",
    "\n",
    "        j = n - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i],nums[j] = nums[j], nums[i]\n",
    "\n",
    "        nums[i + 1: ] = nums[i + 1:][::-1]\n",
    "\n",
    "        res = int(\"\".join(nums))\n",
    "\n",
    "        return res if res < 2 ** 31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "\n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        import heapq\n",
    "        digits = list(str(n))\n",
    "        if len(digits) == 1:\n",
    "            return -1\n",
    "\n",
    "        pq = []\n",
    "        # 然后往前找时，只要有比digit[i]大的，那就换\n",
    "        min_digit = -1\n",
    "        for i in range(len(digits))[::-1]:\n",
    "            for j in range(len(pq)):\n",
    "                if pq[j][0] > digits[i]:\n",
    "                    greater = pq[j][1]\n",
    "                    digits[i],digits[greater] = digits[greater], digits[i]\n",
    "                    num = int(''.join(digits[:i+1] + sorted(digits[i+1:])))\n",
    "                    return num if n < num <= 2 ** 31 - 1 else -1\n",
    "            heapq.heappush(pq, (digits[i],i))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        # 参考题目 https://leetcode.cn/problems/next-permutation/?envType=list&envId=33HH4PJ2\n",
    "        if  n < 10 or n > pow(2,31) -1 :\n",
    "            return -1\n",
    "\n",
    "        nums  = list(str(n))\n",
    "       \n",
    "        i = len(nums) - 2\n",
    "\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "\n",
    "        if i >= 0 :\n",
    "            j = len(nums) - 1\n",
    "            while j > i  and nums[i] >= nums[j]:\n",
    "                j -= 1 \n",
    "            nums[i],nums[j] = nums[j],nums[i]\n",
    "\n",
    "        if i < 0 :\n",
    "            return -1\n",
    "\n",
    "        left ,right = i+1,len(nums) - 1\n",
    "        while left < right :\n",
    "            nums[left],nums[right] = nums[right],nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        n = int(\"\".join(nums))\n",
    "        return n if n <= pow(2,31) -1 else -1 \n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        m = len(nums)\n",
    "        i = m-2\n",
    "\n",
    "        while i>=0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i<0:\n",
    "            return -1\n",
    "\n",
    "        j = m-1\n",
    "        while j>=i and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1:] = nums[i+1:][::-1]\n",
    "        ans = int(\"\".join(nums))\n",
    "        return ans if ans < 2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        if n < 10:\n",
    "            return -1\n",
    "        s = [e for e in str(n)]\n",
    "        nums = [0] * 10\n",
    "        max_num = -1\n",
    "        i = -1\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            x = int(s[i])\n",
    "            if x < max_num:\n",
    "                can = max_num\n",
    "                for j in range(max_num-1, -1, -1):\n",
    "                    if nums[j] > 0 and j>x:\n",
    "                        can = j\n",
    "\n",
    "                nums[x] += 1\n",
    "                s[i] = str(can)\n",
    "                nums[can] -= 1\n",
    "                break\n",
    "            else:\n",
    "                nums[x] += 1\n",
    "                max_num = x\n",
    "        else:\n",
    "            res = int(\"\".join(s))\n",
    "\n",
    "            if res == n or res >= 2147483648:\n",
    "                return -1\n",
    "\n",
    "            return res\n",
    "\n",
    "        p = 0\n",
    "        for i in range(i+1, len(s)):\n",
    "            while nums[p] == 0: p += 1\n",
    "            s[i] = str(p)\n",
    "            nums[p] -= 1\n",
    "\n",
    "        res = int(\"\".join(s))\n",
    "\n",
    "        if res == n or res >= 2147483648:\n",
    "            return -1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        i = n -2\n",
    "\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = n - 1\n",
    "            while j >= i and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        left, right = i+1 , n-1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        \n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        #copy\n",
    "        nums = list(str(n))\n",
    "        i = len(nums)-2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -=1\n",
    "        if i >=0:\n",
    "            j = len(nums)-1\n",
    "            while j >= 0 and nums[i] >= nums[j]:\n",
    "                j-=1\n",
    "            nums[i],nums[j] = nums[j],nums[i]\n",
    "        else:\n",
    "            return -1\n",
    "        left,right = i+1,len(nums)-1\n",
    "        while left < right:\n",
    "            nums[left],nums[right] = nums[right],nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans<=2**31-1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        n=str(n)\n",
    "        if len(n)==1:\n",
    "            return -1\n",
    "        stack=[n[-1]]\n",
    "        for i in range(len(n)-2,-1,-1):\n",
    "            if n[i]>=stack[-1]:\n",
    "                stack.append(n[i])\n",
    "            else:\n",
    "                break\n",
    "        if n[i]<stack[-1]:\n",
    "            for j in range(len(stack)):\n",
    "                if stack[j]>n[i]:\n",
    "                    break\n",
    "            index2=len(n)-1-j\n",
    "            index1=len(n)-1-len(stack)\n",
    "            ret=n[:index1]+n[index2]\n",
    "            stack.pop(j)\n",
    "            judge=0\n",
    "            for i in range(len(stack)):\n",
    "                if stack[i]>n[index1] and judge==0:\n",
    "                    ret+=n[index1]\n",
    "                    judge=1\n",
    "                ret+=stack[i]\n",
    "            if judge==0:\n",
    "                ret+=n[index1]\n",
    "                judge=1\n",
    "            if int(ret)>2147483647:\n",
    "                return -1\n",
    "            return int(ret)\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        s = list(str(n))\n",
    "        exchange = False\n",
    "        for i in range(len(s)-1, 0, -1):\n",
    "            if s[i] > s[i-1]:\n",
    "                index = i\n",
    "                min_big = s[i]\n",
    "                for j in range(i, len(s)):\n",
    "                    if s[i-1] < s[j] < min_big:\n",
    "                        min_big = s[j]\n",
    "                        index = j\n",
    "                s[i-1], s[index] = s[index], s[i-1]\n",
    "                tmp = s[i:]\n",
    "                tmp.sort()\n",
    "                s = s[:i]\n",
    "                s.extend(tmp)\n",
    "                exchange = True\n",
    "                break\n",
    "        ret = int(''.join(s))\n",
    "        max_int = (1 << 31) -1\n",
    "        if exchange and ret <= max_int: \n",
    "            return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "      array = []\n",
    "      while n != 0:\n",
    "        if len(array) == 0:\n",
    "          array.append(n % 10)\n",
    "          n //= 10\n",
    "        else:\n",
    "          temp = n % 10\n",
    "          if temp < array[-1]:\n",
    "            ind = len(array) - 2\n",
    "            while ind != -1 and temp < array[ind]:\n",
    "              ind -= 1\n",
    "            n = n - temp + array[ind+1]\n",
    "            for i in range(len(array)):\n",
    "              if i != ind + 1:\n",
    "                n = n * 10 + array[i]\n",
    "              else:\n",
    "                n = n * 10 + temp\n",
    "\n",
    "            if n >= 2147483648:\n",
    "              return -1\n",
    "            else:\n",
    "              return n\n",
    "          else:\n",
    "            array.append(temp)\n",
    "            n //= 10\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def nextGreaterElement(self, n: int) -> int:\r\n",
    "        s = list(str(n))\r\n",
    "        i = len(s) - 1\r\n",
    "        while i > 0 and s[i - 1] >= s[i]:\r\n",
    "            i -= 1\r\n",
    "        if i == 0:\r\n",
    "            return -1\r\n",
    "        j = i\r\n",
    "        while j + 1 < len(s) and s[j + 1] > s[i - 1]:\r\n",
    "            j += 1\r\n",
    "        s[i - 1], s[j] = s[j], s[i - 1]\r\n",
    "        s[i:] = s[i:][::-1]\r\n",
    "        res = int(''.join(s))\r\n",
    "        return res if res < 2**31 else -1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        #print(int(2**32),int(2**31-1))\n",
    "        n=str(n)\n",
    "        mark=-1\n",
    "        for i in range(1,len(n))[::-1]:\n",
    "            if n[i-1]<n[i]:\n",
    "                mark=i-1\n",
    "                break\n",
    "        if mark==-1:\n",
    "            return -1\n",
    "        for i in range(1,len(n))[::-1]:\n",
    "            if n[i]>n[mark]:\n",
    "                break\n",
    "        n=n[:mark]+n[i]+(n[(mark+1):i]+n[mark]+n[(i+1):])[::-1]\n",
    "\n",
    "        if int(n)<=2**31-1:\n",
    "            return int(n)\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "\n",
    "        num = [int(i) for i in str(n)]\n",
    "\n",
    "        i = len(num)-2\n",
    "        while i>=0 and num[i]>=num[i+1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "        \n",
    "        j = len(num) - 1\n",
    "        while j>=0 and num[i]>=num[j]:\n",
    "            j -= 1\n",
    "        num[i], num[j] = num[j], num[i]\n",
    "        num[i+1:] = num[i+1:][::-1]\n",
    "        ans = int(''.join([str(i) for i in num]))\n",
    "        return ans if ans < 2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        # a = []\n",
    "        # while n:\n",
    "        #     a.append(n % 10)\n",
    "        #     n = n // 10\n",
    "        # m = len(a)\n",
    "        # if m == 1:\n",
    "        #     return -1\n",
    "        # # print(a)\n",
    "        # tmp = deque()\n",
    "        # tmp.append(a[0])\n",
    "        # l = 1\n",
    "        # while 0 < l < m and a[l-1] <= a[l]:\n",
    "        #     tmp.append(a[l])\n",
    "        #     l += 1\n",
    "        # # print(l)\n",
    "        # if l == m: # 最后一个数，没有逆序对\n",
    "        #     return -1\n",
    "        # while tmp and tmp[-1] > a[l]:\n",
    "        #     tmp.pop()\n",
    "        # a[l],a[len(tmp)] = a[len(tmp)],a[l]\n",
    "        # res = 0\n",
    "        # cal = 0\n",
    "        # for i in range(l-1,-1,-1):\n",
    "        #     res += a[i]*10**cal\n",
    "        #     cal += 1\n",
    "        # for i in range(l,m):\n",
    "        #     res += a[i]*10**cal\n",
    "        #     cal += 1\n",
    "        # if res > 2**31 - 1:\n",
    "        #     return -1\n",
    "        # return res\n",
    "        \n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(n % 10)\n",
    "            n = n // 10\n",
    "        m = len(a)\n",
    "        a.reverse()\n",
    "        for i in range(m-1,0,-1):\n",
    "            if a[i-1] < a[i]: # 最小值是i-1\n",
    "                for j in range(m-1,i-1,-1):\n",
    "                    if a[i-1] < a[j]:\n",
    "                        a[i-1], a[j] = a[j], a[i-1]\n",
    "                        break\n",
    "                l,r = i,m-1\n",
    "                while l <= r:\n",
    "                    a[l],a[r] = a[r],a[l]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                res = int(''.join(list(map(str,a))))\n",
    "                print(res)\n",
    "                return (-1 if res > 2**31 - 1 else res)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        def get_next(n):\n",
    "            s = str(n)\n",
    "            i = len(s) - 1\n",
    "            while i >= 1:\n",
    "                if s[i] > s[i-1]:\n",
    "                    i -= 1\n",
    "                    break\n",
    "                i -= 1\n",
    "\n",
    "            if i == 0 and s[i] > s[i + 1]:\n",
    "                return int(s[::-1])\n",
    "            \n",
    "            j = len(s) - 1\n",
    "            while j >= 0:\n",
    "                if s[j] > s[i]:\n",
    "                    break \n",
    "                j -= 1\n",
    "            \n",
    "            res = s[:i] + s[j] + s[len(s)-1:j:-1] + s[i] + s[j-1:i:-1]\n",
    "            return int(res)\n",
    "\n",
    "        if len(str(n)) <= 1:\n",
    "            return -1\n",
    "\n",
    "        if get_next(n) > n and get_next(n) < pow(2, 31):\n",
    "            return get_next(n)\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "        \n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1:] = nums[i+1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2**31 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        x = n\n",
    "        nums = []\n",
    "        while x:\n",
    "            nums.insert(0,x%10)\n",
    "            x = int(x // 10)\n",
    "\n",
    "        index = len(nums)-1\n",
    "        k = -1\n",
    "        while index>=0:\n",
    "            for i in range(len(nums)-1,index,-1):\n",
    "                if nums[i]>nums[index]:\n",
    "                    k = i\n",
    "                    break\n",
    "            if k>=0:\n",
    "                break\n",
    "            else:\n",
    "                index-=1\n",
    "        if k>=0:\n",
    "            t = nums[index]\n",
    "            nums[index] = nums[k]\n",
    "            nums[k] = t\n",
    "            nums[index+1:] = sorted(nums[index+1:])\n",
    "            ans = int(''.join([str(i) for i in nums]) )\n",
    "            if ans>2**31-1:\n",
    "                return -1\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list((str(n)))\n",
    "        i = len(nums)-2\n",
    "        while i >= 0 and nums[i] >= nums[i+1]:\n",
    "            i -= 1\n",
    "        if i >= 0:\n",
    "            j = len(nums)-1\n",
    "            while j >= 0 and nums[i] >= nums[j]:\n",
    "                j -= 1\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "        else:\n",
    "            return -1\n",
    "        left, right = i+1, len(nums)-1\n",
    "        while left < right:\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        ans = int(\"\".join(nums))\n",
    "        return ans if ans <= (2**31-1) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        l = str(n)\n",
    "        l = list(l)\n",
    "\n",
    "        for i in range(len(l)-2, -1, -1):\n",
    "            for j in range(len(l)-1, i, -1):\n",
    "                if l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "                    tmp = l[i+1:]\n",
    "                    tmp.sort()\n",
    "                    \n",
    "                    res = int(\n",
    "                        \"\".join(l[:i+1]) + \"\".join(tmp)\n",
    "                    )\n",
    "\n",
    "                    if res == n or res > 2 ** 31 - 1:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        return res\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        s = [int(num) for num in str(n)[::-1]]\n",
    "        stack = []\n",
    "        for i, num in enumerate(s):\n",
    "            if not stack or num >= stack[-1]:\n",
    "                stack.append(num)\n",
    "            else:\n",
    "                cur = 0\n",
    "                while cur < len(stack):\n",
    "                    if stack[cur] > num:  #找到遍历过的、比num大的数字中最小的那个\n",
    "                        s[i] = stack[cur]\n",
    "                        stack[cur] = num\n",
    "                        stack.sort(reverse = True)\n",
    "                        for j, new in enumerate(stack):  #把遍历过的数字排序\n",
    "                            s[j] = new\n",
    "                        news = [str(num) for num in s]\n",
    "                        ret = int(''.join(reversed(news)))\n",
    "                        return ret if ret < 2 ** 31 else -1\n",
    "                    else:\n",
    "                        cur += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        arr,index,flag=[],0,False\n",
    "        while n:\n",
    "            a=n%10\n",
    "            if arr:\n",
    "                if a<arr[-1]:\n",
    "                    flag=True\n",
    "            arr.append(a)\n",
    "            if not flag:\n",
    "                index+=1\n",
    "            n//=10\n",
    "        if not flag:\n",
    "            return -1\n",
    "        for i in range(index):\n",
    "            if arr[i]>arr[index]:\n",
    "                arr[i],arr[index]=arr[index],arr[i]\n",
    "                break\n",
    "        arr=sorted(arr[:index],reverse=True)+arr[index:]\n",
    "        for num in arr[::-1]:\n",
    "            n=n*10+num\n",
    "        return n if 1<=n<2**31 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        # l = list(str(n))\n",
    "        # used = [0] * len(l)\n",
    "        # def backtracking(nums, path, result, used):\n",
    "        #     if not nums:\n",
    "        #         return 0\n",
    "        #     if len(path) == len(nums):\n",
    "        #         result.append(int(\"\".join(path[:])))\n",
    "        #         # return \n",
    "        #     for i in range(len(nums)):\n",
    "        #         if used[i]:\n",
    "        #             continue\n",
    "        #         used[i] = 1\n",
    "        #         path.append(nums[i])\n",
    "        #         backtracking(nums, path, result, used)\n",
    "        #         path.pop()\n",
    "        #         used[i] = 0\n",
    "        #     return result\n",
    "        # res = backtracking(l, [], [], used)\n",
    "        # res.sort()\n",
    "        # idx = res.index(n)\n",
    "        # for i in range(idx+1, len(res)):\n",
    "        #     if res[i] > res[i-1]:  \n",
    "        #         if res[i] >= 2 ** 31:\n",
    "        #             return -1               \n",
    "        #         return res[i]\n",
    "        #     elif res[i] == res[i-1]:\n",
    "        #         continue                      \n",
    "        # return -1\n",
    "        def getnum(n):\n",
    "            nums = list(str(n))\n",
    "            index = -1\n",
    "            for i in range(len(nums)-2, -1, -1):\n",
    "                if nums[i] < nums[i+1]:\n",
    "                    index = i\n",
    "                    break\n",
    "            if index == -1:\n",
    "                nums.reverse()\n",
    "                return nums\n",
    "            for i in range(len(nums)-1, index, -1):\n",
    "                if nums[i] > nums[index]:\n",
    "                    nums[index], nums[i] = nums[i], nums[index]\n",
    "                    break\n",
    "            left = index + 1\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                if nums[left] > nums[right]:\n",
    "                    nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return nums\n",
    "        nxt = int(\"\".join(getnum(n)))   \n",
    "        if nxt > n and nxt <= 2**31-1:\n",
    "            return nxt\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums=list(str(n))\n",
    "        i=len(nums)-2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "        j=len(nums)-1\n",
    "        while j>=0 and nums[i]>=nums[j]:\n",
    "            j-=1\n",
    "        nums[i],nums[j]=nums[j],nums[i]\n",
    "        nums[i+1:]=nums[i+1:][::-1]\n",
    "        ans=int(''.join(nums))\n",
    "        return ans if ans<=2**31-1 else -1\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, n: int) -> int:\n",
    "        nums = list(str(n))\n",
    "        i = len(nums) - 2\n",
    "        while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "            i -= 1\n",
    "        if i < 0:\n",
    "            return -1\n",
    "        \n",
    "        j = len(nums) - 1\n",
    "        while j >= 0 and nums[i] >= nums[j]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1:] = nums[i + 1:][::-1]\n",
    "        ans = int(''.join(nums))\n",
    "        return ans if ans < 2 ** 31 else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
